# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

from Graph import Graph
from Matrix import Matrix

class AdjMatrixGraph(Graph):

    def __init__(self, multi=False, directed=False):
        Graph.__init__(self, multi, directed)
        self.adj_matrix = Matrix()
        self._E = 0

    def add_edge(self, u, v):
        _max = max(u,v)
        if self.V() - 1 < _max:
            self.adj_matrix.extend(_max+1, _max+1)
        self.adj_matrix[u][v] = 1
        self._E += 1
        if not self.directed:
            self.adj_matrix[v][u] = 1
            self._E += 1

    def add_vertex(self, u):
        if self.V() - 1 < u:
            self.adj_matrix.extend(u+1, u+1)

    def V(self):
        return self.adj_matrix.rows_count()

    def E(self):
        return self._E

    def degree_in(self, u):
        "O(|V|)/O(1)"
        return sum (self.adj_matrix.column(u))

    def degree_out(self, u):
        "O(|V|)/O(1)"
        return sum (self.adj_matrix.row(u))

    def transpose(self):
        "O(|V|^2)/O(1)"
        self.adj_matrix.transpose()

    def unmulti(self):
        "O(|V|^2)/O(1)"
        for u in xrange (self.adj_matrix.rows_count()):
            for v in xrange (self.adj_matrix.columns_count()):
                if u == v:
                    self.adj_matrix[u][u] = 0
                elif self.adj_matrix[u][v] > 1:
                    self.adj_matrix[u][v] = 1

    def square(self):
        "O(|V|^3)/O(|V|^2)"
        self.adj_matrix = Matrix.mul (self.adj_matrix, self.adj_matrix)

    def vertices(self):
        "O(1)/O(1)"
        return xrange(self.adj_matrix.rows_count())

    def edges(self):
        for u, urow in enumerate(self.adj_matrix.rows()):
            for v, uv in enumerate(urow):
                if uv:
                    yield (u,v)

    def universal_sink(self):
        "O(|V|)/O(1)"
        sink = None
        u = 0
        v = self.adj_matrix.rows_count() - 1
        while (v - u) > 0:
            a = self.adj_matrix[v][u]
            b = self.adj_matrix[u][v]
            u, v = u + (1-a) + a*b, v - (1-b) - a*b
        if u == v:
            sink = u
            for i in xrange(self.adj_matrix.rows_count()):
                if (i != u) and (self.adj_matrix[i][u] == 0):
                    sink = None
                    break
            if sink:
                for j in xrange(self.adj_matrix.columns_count()):
                    if self.adj_matrix[u][i] != 0:
                        sink = None
                        break
        return sink

    def neighbours(self, u):
        "O(|V|)/O(|V|)"
        ret = []
        for v in self.vertices():
            if self.adj_matrix[u][v] > 0:
                ret.extend ([v] * self.adj_matrix[u][v])
        return ret
